/*
 * Greedy, BFS-like.
 * Not working on graphs with negative edge weights.
 */
#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
using namespace std;

struct vertex_t
{
    vector<pair<vertex_t *, int> > adjacent;
    bool known;
    int value;
    int distance;
    vertex_t *path;
public:
    vertex_t(int v) : known(false), value(v), distance(INT_MAX), path(NULL) { }
};

void dijkstra(vertex_t *vt, int n, int i)
{
    vt[i].distance = 0;
    while (true) {
        vertex_t *v = NULL;
        /* find a shortest unknown distance vertex */
        for (int j = 0; j < n; j++) {
            if (!vt[j].known
                && (!v || (v->distance > vt[j].distance))) {
                v = &vt[j];
            }
        }
        if (!v) {
            break;
        }
        v->known = true;
        for (vector<pair<vertex_t *, int> >::const_iterator it = v->adjacent.begin();
            it != v->adjacent.end(); it++) {
            if (!it->first->known) {
                if (it->first->distance > (v->distance + it->second)) {
                    it->first->distance = (v->distance + it->second);
                    it->first->path = v;
                }
            }
        }
    }
}

/* no label version */
void dijkstra2(vertex_t *vt, int n, int i)
{
    vt[i].distance = 0;
    vector<vertex_t *> vs;
    for (int i = 0; i < n; i++) {
        vs.push_back(&vt[i]);
    }
    while (!vs.empty()) {
        vertex_t *v = NULL;
        /* find a shortest unknown distance vertex */
        for (vector<vertex_t *>::const_iterator it = vs.begin(); it != vs.end(); it++) {
            if (!v || (v->distance > (*it)->distance)) {
                v = *it;
            }
        }
        if (!v) {
            break;
        }
        vs.erase(std::find(vs.begin(), vs.end(), v));
        for (vector<pair<vertex_t *, int> >::const_iterator it = v->adjacent.begin();
            it != v->adjacent.end(); it++) {
            if (std::find(vs.begin(), vs.end(), it->first) != vs.end()) {
                if (it->first->distance > (v->distance + it->second)) {
                    it->first->distance = (v->distance + it->second);
                    it->first->path = v;
                }
            }
        }
    }
}

/* works with negative edge weights. */
bool ford(vertex_t *vt, int n, int i)
{
    vt[i].distance = 0;
    vector<vertex_t *> vs;
    for (int i = 0; i < n; i++) {
        vs.push_back(&vt[i]);
    }
    /* for each vertex */
    for (int i = 0; i < n; i++) {
        /* for each edge */
        for (int j = 0; j < n; j++) {
            vector<pair<vertex_t *, int> > &adj = vs[j]->adjacent;
            for (int k = 0; k < adj.size(); k++) {
                /* check overflow */
                if (vs[j]->distance != INT_MAX
                    && adj[k].first->distance > vs[j]->distance + adj[k].second) {
                    adj[k].first->distance = vs[j]->distance + adj[k].second;
                    adj[k].first->path = vs[j];
                }
            }
        }
    }
    /* check for negative weight cycles */
    for (int j = 0; j < n; j++) {
        vector<pair<vertex_t *, int> > &adj = vs[j]->adjacent;
        for (int k = 0; k < adj.size(); k++) {
            if (adj[k].first->distance > vs[j]->distance + adj[k].second) {
                cout << "negative weight cycle detected..." << endl;
                return false;
            }
        }
    }
    return true;
}

void print(const vertex_t &v)
{
    if (v.path) {
        print(*v.path);
        cout << " -> ";
    }
    cout << v.value;
}

int main()
{
//#define _FORD
    vertex_t vt[] = { 0, 1, 2, 3, 4, 5, 6, 7 };
    vt[1].adjacent.push_back(pair<vertex_t *, int>(&vt[2], 2));
#ifndef _FORD
    vt[1].adjacent.push_back(pair<vertex_t *, int>(&vt[4], 1));
#else
    vt[1].adjacent.push_back(pair<vertex_t *, int>(&vt[4], -10)); /* add a negative weight cycle */
#endif
    vt[2].adjacent.push_back(pair<vertex_t *, int>(&vt[4], 3));
    vt[2].adjacent.push_back(pair<vertex_t *, int>(&vt[5], 10));
    vt[3].adjacent.push_back(pair<vertex_t *, int>(&vt[1], 4));
    vt[3].adjacent.push_back(pair<vertex_t *, int>(&vt[6], 5));
    vt[4].adjacent.push_back(pair<vertex_t *, int>(&vt[3], 2));
    vt[4].adjacent.push_back(pair<vertex_t *, int>(&vt[5], 2));
    vt[4].adjacent.push_back(pair<vertex_t *, int>(&vt[6], 8));
    vt[4].adjacent.push_back(pair<vertex_t *, int>(&vt[7], 4));
    vt[5].adjacent.push_back(pair<vertex_t *, int>(&vt[7], 6));
    vt[7].adjacent.push_back(pair<vertex_t *, int>(&vt[6], 1));
#ifndef _FORD
    dijkstra(vt, sizeof(vt)/sizeof(vt[0]), 1); /* start from vt[1] */
    print(vt[6]); /* print path from vt[1] to vt[6] */
#else
    bool rc = ford(vt, sizeof(vt)/sizeof(vt[0]), 1); /* start from vt[1] */
    if (rc) {
        print(vt[6]); /* print path from vt[1] to vt[6] */
    }
#endif
    cout << endl;
    return 0;
}
